//
//  Problem106.swift
//  TestProject
//
//  Created by 武侠 on 2021/5/25.
//  Copyright © 2021 zhulong. All rights reserved.
//

import UIKit

/*
 106. 从中序与后序遍历序列构造二叉树
 根据一棵树的中序遍历与后序遍历构造二叉树。

 注意: 你可以假设树中没有重复的元素。

 例如，给出

 中序遍历 inorder   = [9,3,15,20,7]
 后序遍历 postorder = [9,15,7,20,3]
 返回如下的二叉树：

     3
    / \
   9  20
     /  \
    15   7
 */
@objcMembers class Problem106: NSObject {
    func solution() {
//        let root = buildTree([9,3,15,20,7], [9,15,7,20,3])
        let root = buildTree([2,1], [2,1])
//        let root = buildTree([1,2], [2,1])
        print(printNodeTree(root))
    }
    
    /*
     递归
     1：后续遍历数组的最后一位肯定是根root，那么我们就根据root把中续数组切割成2个 left 和 right
     2: 切割完后，我们知道left和right的个数，那么我们就能根据个数把后续遍历切割
     3: 继续递归
     
     */
    func buildTree(_ inorder: [Int], _ postorder: [Int]) -> TreeNode? {
        return buildTreeDi(inorder, 0, inorder.count-1, postorder, 0, postorder.count-1)
    }
    
    func buildTreeDi(_ inorder: [Int], _ inLeft: Int, _ inRight: Int, _ postorder: [Int], _ postLeft: Int, _ postRight: Int) -> TreeNode? {
        if inRight < inLeft || postRight < postLeft {
            return nil
        }
        if inLeft == inRight {
            return TreeNode(inorder[inLeft])
        }
        
        // 后续遍历的最后一位 就是根
        let root = TreeNode(postorder[postRight])
        // 根据根，把中续遍历进行切割
        let rootValue = postorder[postRight]
        var rootIndex = -1
        print(inLeft, inRight)
        for i in inLeft...inRight {
            if inorder[i] == rootValue {
                rootIndex = i
            }
        }
        if rootIndex == -1 {
            return nil
        }
        print(inLeft, rootIndex-1, postLeft, postLeft+rootIndex-inLeft-1)
        root.left  = buildTreeDi(inorder, inLeft, rootIndex-1, postorder, postLeft, postLeft+rootIndex-inLeft-1)
        
        print(rootIndex+1, inRight, postLeft+rootIndex-inLeft, postRight-1)
        root.right = buildTreeDi(inorder, rootIndex+1, inRight, postorder, postLeft+rootIndex-inLeft, postRight-1)
        
        return root
    }
    
    /*
     迭代 
     */
    
}
